package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 655. 输出二叉树
 * @author feizns
 * @since 2020/3/10
 */
public class PrintTree {

    public static void main(String[] args) {
        System.out.println(death(new TreeNode(1), 0));
    }

    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> ret = new LinkedList<>();
        if ( root != null ) {
            int d = death(root, 0);
            int c = ((d - 1) * 2) + 1;
            for (int i = 0; i < d; i++) {
                List<String> row = new ArrayList<>();
                for (int j = 0; j < c; j++)
                    row.add("");
                ret.add(row);
            }
            setTree(root, ret, 0, 0, c - 1);
        }
        return ret;
    }

    private void setTree(TreeNode root, List<List<String>> lists, int level, int l, int r) {
        if ( root != null ) {
            List<String> list = lists.get(level);
            int mid = l + (r - l) / 2;
            list.set(mid, root.val + "");
            setTree(root.left, lists, level + 1, l, mid - 1);
            setTree(root.right, lists, level + 1, mid + 1, r);
        }
    }

    private static int death(TreeNode node, int d) {
        return node != null ? Math.max(death(node.left, d), death(node.right, d)) + 1 : d;
    }

}
